metatilities, конечно, весьма удобная помойка, но структуры данных там реально тормознутые за счёт тяжелейшего CLOS :(

Для нормального, более-менее универсального priority queue пришлось какое-то время покопать интернет, но, к счастью, что-то нашлось у небезысвестного Nikodemus Siivola: heap, priority queue, lisp, data structure, common lisp